﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
//剑指 Offer II 070. 排序数组中只出现一次的数字❤️
class Solution {
public:
	int singleNonDuplicate(vector<int>& nums)
	{
		int low = 0, high = nums.size() - 1;
		while (low < high)
		{
			int mid = (high + low) / 2;
			mid -= mid & 1;
			if (nums[mid] == nums[mid + 1])
			{
				low = mid + 2;
			}
			else
			{
				high = mid;
			}
		}
		return nums[low];
	}
};

//剑指 Offer II 071. 按权重生成随机数❤️
class Solution {
public:
	vector<int>preSum;
	Solution(vector<int>& w) {
		int n = w.size();
		preSum = vector<int>(n + 1, 0);
		for (int i = 0; i < n; i++)
		{
			preSum[i + 1] = preSum[i] + w[i];
		}
	}

	int pickIndex()
	{
		int target = rand() % preSum.back() + 1;
		int left = 0, right = preSum.size();
		while (left < right)
		{
			int mid = (left + right) / 2;
			if (preSum[mid] < target)
			{
				left = mid + 1;
			}
			else
			{
				right = mid;
			}
		}
		return left - 1;
	}
};